package mo.leetcode_top;

public class L378 {

    public int kthSmallest(int[][] matrix, int k) {
        int left = matrix[0][0];
        int m = matrix.length;
        int n = matrix[0].length;
        int right = matrix[m-1][n-1];
        while (left < right) {
            int mid = (left + right) / 2;
            int cnt = 0;
            for (int i = 0; i < m; i++) {
                if (mid > matrix[i][n-1]) {
                    cnt += n;
                } else if (mid >= matrix[i][0]) {
                    cnt++;
                    for (int j = 1; j < n; j++) {
                        if (mid >= matrix[i][j]) {
                            cnt++;
                        }
                    }
                }

            }
            if (cnt < k) {
                left = mid + 1;
            } else {
                if (right == mid) {
                    break;
                }
                right = mid;
            }

        }
        return left;

    }

    public static void main(String[] args) {
        L378 test = new L378();
        System.out.println(test.kthSmallest(new int[][]{{-5, -4}, {-5, -4}}, 2));
    }

}
